package leetcode.set_map;


import java.util.TreeSet;

/**
 * 220. 存在重复元素 III
 * <p>
 * 给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,2,3,1], k = 3, t = 0
 * 输出: true
 * <p>
 * 示例 2:
 * <p>
 * 输入: nums = [1,0,1,1], k = 1, t = 2
 * 输出: true
 * <p>
 * 示例 3:
 * <p>
 * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
 * 输出: false
 * 首先分析： 219号问题反馈的是nums[i]==nums[j]
 * 这里反馈两个数绝对值之差的最大值为t  也就是说 Math.abs(i,j)<=t;  i-j> -t </=t;>
 * 我们需要使用set进程存放当前元素，如果长度超过k 则进行删除num[i-k] 使用set进行删除一个元素 TreeSet 时间复杂度O(log(n))
 * 还是不太懂这个题---以后好好研究一下
 */
public class Solution220 {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            //元素 | nums[i]-nums[j] | <=t
            //ceiling 比它nums[i] - t大的最小值
            //化简式子得： nums[j]<=nums[i]+t; nums[i]-t<=nums[j]  所以求取ceil比他大的最小值。
            if (set.ceiling(((long) nums[i] - (long) t)) != null && set.ceiling(((long) nums[i] - (long) t)) <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (set.size() == k + 1)
                set.remove((long) nums[i - k]);
        }
        return false;
    }

}
